首页 > 试题广场 >

二维数组中的查找

[编程题]二维数组中的查找
  • 热度指数：2367261 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 ， 矩阵中的值满足
进阶：空间复杂度 ，时间复杂度
示例1

输入

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

true

说明

存在7，返回true
示例2

输入

1,[[2]]

输出

false
示例3

输入

3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

false

说明

不存在3，返回false
算法知识视频讲解
查看答案及解析
添加回答
推荐
徘徊的路人甲头像 徘徊的路人甲 
/* 思路
* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时，上移
*/

class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        int rowCount = array.size();
        int colCount = array[0].size();
        int i,j;
        for(i=rowCount-1,j=0;i>=0&&j<colCount;)
        {
            if(target == array[i][j])
                return true;
            if(target < array[i][j])
            {
                i--;
                continue;
            }
            if(target > array[i][j])
            {
                j++;
                continue;
            }
        }
        return false;
    }
};

编辑于 2015-06-18 16:50:07 回复(249)
JavaScript Node
极品光头强头像 极品光头强 
function Find( target ,  array ) {    
    return array.flat(Infinity).includes(target);
}
module.exports = {
    Find : Find
};

发表于 2023-10-19 16:32:03 回复(0)
JavaScript Node
达拉崩吧、头像 达拉崩吧、
利用矩阵的特点，
从左下角开始向右上角（或反过来）走，（如果从左上，则选择不唯一，不好做）
target偏小，则向上走；偏大则向右走，直到找到或者走出矩阵。 
function Find( target ,  array ) {
    const row = array.length;
    if(row === 0)
        return false;
    const col = array[0].length;
    if(col === 0)
        return false;
    // 从左下角开始走
    let i = row - 1;
    let j = 0;
    while(i >= 0 && j <= col - 1){
        if(target === array[i][j]){
            return true;
        } else if(target < array[i][j]){
            i--;
        } else {
            j++;
        }
    }
    return false;
}


发表于 2023-08-12 16:15:50 回复(0)
JavaScript Node
牛客87740779号头像 牛客87740779号

题解是抄的，为了我之后更方便找而已

题目所提供的矩阵，是一种特殊的矩阵，称作杨氏矩阵，其有特定的查找算法，时间复杂度 m,n分别为矩阵的两个维度。查找算法步骤如下：

1.从矩阵的左下角或者矩阵的右上角处开始递归运行，以左下角为例，value为要查找的值，(i,j)为当前矩阵中的位置，初始为(M-1, 0)

2.如果超过了矩阵范围则说明不存在这样的元素，返回false

3.否则的话，如果当前位置的值大于value，说明要移动位置(向上移一行)，使得数值减小，即递归使得i=i-1；如果当前位置的值小于value，说明要移动位置(向右移一列)，使得数值增大，即递归使得j=j+1；如果刚好等于value，返回当前的位置true即可

alt

查找过程如红色箭头所示：

我们在6的位置，发现6比12小，那么6上面的数比6小，右边的数比6大，那么只能向右边走

同理在8，11，一样

当移动到了15，15比12大，那么12一定在15的上方，向上移动

同理在13一样，最后在12处找到了目标值。 
function Find(target, array)
{
  //判断数组是否为空
  let m = array.length;
  if(m == 0)  return false;
  
  let n = array[0].length;
  if(n == 0)  return false;
  
  let i=0, j=n-1;//右上角元素
  while(i<m && j>=0){
    if(target < array[i][j]){
      j--;
    }else if(target > array[i][j]){
      i++;
    }else{
      return true;
    }
  }
  return false;
}
module.exports = {
    Find : Find
};


发表于 2022-10-15 10:05:36 回复(0)
JavaScript Node
茅台兑红茶头像 茅台兑红茶
非二分查找法
二维降一维，用 includes 或 indexOf 查找 
function Find(target, array)
{
    // write code here
    let arr = array.flat()
    return arr.includes(target)    
}
module.exports = {
    Find : Find
};


发表于 2022-10-12 14:14:31 回复(0)
JavaScript Node
公主从不秃头头像 公主从不秃头
function Find(target, array)
{
    // write code here
    let len1 = array.length
    let len2 = array[0].length
    if(!len1||!len2) return false
    if(len1==1){
        for(var i=0;i<len2;i++){
            if(target == array[i])return true
        }
        return false
    }
    else{
        for(var i=0;i<len1;){
            for(var j=len2-1;j>=0;){
                if(target == array[i][j]) return true;
                else if(target > array[i][j])i++;
                else j--;
            
                if(i<0||j<0||i>=len1||j>=len2) return false
                
            }
        }
        return false
    }
    
}
module.exports = {
    Find : Find
};
发表于 2022-09-08 11:01:42 回复(0)
JavaScript Node
牛客67815066号头像 牛客67815066号
简洁的JavaScript: 
function Find(target, array)
{
    // write code here
    for (let i = 0; i < array.length; i++){
        let smallest = array[i][0];
        let largest = array[i][array.length - 1];
        if (target >= smallest && target <= largest) {
            if (array[i].includes(target)) return true;
        }
    }
    return false;
}


发表于 2021-09-27 18:16:40 回复(0)
JavaScript Node
风随你行头像 风随你行
我是直接用includes判断二位数组是否有该元素，用some在找到元素之后自动退出循环
let flag = array.some((value) => {
        return value.includes(target)
    });
    return flag;


发表于 2021-08-09 21:07:03 回复(0)
JavaScript Node
周欣仪头像 周欣仪
因为数组都是从左到右，从上到下递增的，因此比较的时候是有规律的。
我们可以从数组的右上角开始进行比较。
分为以下两种情况：
1、当目标数字比右上角的数字小时；
因为右上角的数字是它那一列中最小的，那么目标数字一定比右上角那一列的数字都小。
就没有比较的必要了，因此，可以将比较的数字左移一排，继续进行比较。

2、当目标数字比右上角的数字大时；
右上角的数字是那一行中最大的，因此目标数字比哪一行的数字都大，那一行也没有继续比下去的必要了。
因此将右上角的数字下移一位，继续进行比较，直到找完或者找到为止。
代码如下所示： 
function Find(target, array)
{
    // write code here
    let lenx=array.length
    let lenY=array[0].length
    for(var i=array.length-1,j=0;i>=0 && j<lenY;)
        {
            if(target<array[i][j])
                {
                    i--
                }
            else if(target > array[i][j])
                {
                    j++
                }
            else{
                return true
            }
        }
}


发表于 2021-08-08 14:49:04 回复(4)
提交观点

问题信息

数组
来自：2015年度信息化技能...
难度：
9条回答 1521018浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号